#include <iostream>
#include <vector>
using namespace std;

void AdjustUp(vector<int>& arr, int i)
{
	int child = i, parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			swap(arr[child], arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;

	}
}



void HeapSort_Up(vector<int>& arr)
{
	int n = arr.size();
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(arr, i);
	}

	for (int i = n - 1; i >= 0; --i)
	{
		swap(arr[i], arr[0]);
		for (int j = 0; j < i; ++j)
		{
			AdjustUp(arr, j);
		}
	}
}

void AdjustDown(vector<int>& arr, int i, int n)
{
	int parent = i, child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
			child++;
		if (arr[child] > arr[parent])
		{
			swap(arr[child], arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;

	}
}

void HeapSort_Down(vector<int>& arr)
{
	int n = arr.size();
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, i, n);
	}
	for (int i = n - 1; i >= 0; --i)
	{
		swap(arr[0], arr[i]);
		AdjustDown(arr, 0, i);
	}
}

int main()
{
	vector<int> arr = { 1, 8, 9, 3, 5, 20, 4, 34, 53, 2, 0, 7 };
	HeapSort_Up(arr);
	for (auto e : arr)
		cout << e << " ";
	cout << endl;
	return 0;
}